package leetcode.dp;


public class A64 {
    //暴力递归
    public int minPathSum1(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        return f1(n - 1, m - 1, grid);
    }
    int f1(int n, int m, int[][] grid) {
        if (n == 0 && m == 0) return grid[0][0];
        //返回左和上的较小值加上自己
        int up = Integer.MAX_VALUE;
        int left = Integer.MAX_VALUE;
        if (n > 0) up = f1(n - 1, m, grid);
        if (m > 0) left = f1(n, m - 1, grid);
        return Math.min(up, left) + grid[n][m];
    }
    //记忆化搜索优化
    public int minPathSum2(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        return f2(n - 1, m - 1, grid, dp);
    }
    int f2(int n, int m, int[][] grid, int[][] dp) {
        if (n == 0 && m == 0) return grid[0][0];
        //返回左和上的较小值加上自己
        if (dp[n][m] != 0) return dp[n][m];
        int up = Integer.MAX_VALUE;
        int left = Integer.MAX_VALUE;
        if (n > 0) up = f2(n - 1, m, grid, dp);
        if (m > 0) left = f2(n, m - 1, grid, dp);
        dp[n][m] = Math.min(up, left) + grid[n][m];
        return dp[n][m];
    }
    //知道是由左和上更新后
    //直接动态规划
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        //先初始化左侧和上侧
        dp[0][0] = grid[0][0];
        //上
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        //左
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][m - 1];
    }

}
